The invention relates to memory management and in particular, to a tag controlled prefetch buffer management system that is part of a cache system.
In processing systems such as computers, the data to be utilized by a processor is stored in a memory (e.g., main memory, lower level memory) and control logic manages the transfer of data between the memory and the processor in response to requests issued by the processor. The data stored in the main memory generally includes both instructions to be executed by the processor and data to be operated on by the processor. For simplicity, both instructions and true data are referred to collectively herein as “data” unless the context requires otherwise. The time taken by a main memory access is relatively long in relation to the operating speeds of modern processors. To address this, a cache memory with a shorter access time is generally interposed between the main memory and the processor, and the control logic manages the storage of data retrieved from the main memory in the cache and the supply of data from the cache to the processor.
A typical cache is organized into multiple “lines”, each line providing storage for a line of data from the main memory which may be many bytes in length. When the processor issues a request for data contained in a particular line in a page, or block, the control logic determines whether that line is stored in the cache. If the line is stored in cache (i.e., there is a cache hit), the data is retrieved from the cache. If the line is not stored in cache (i.e., there is a cache miss), the data must be retrieved from the main memory and the processor is stalled while this operation takes place. Since a cache access is much faster than a lower level memory access, it is clearly desirable to manage the system so as to achieve a high ratio of cache hits to cache misses.
Memory latency is becoming an increasingly important factor in computer system performance. An implication of this increasing importance is that cache faults from the slowest on-chip cache are becoming more expensive in terms of performance. One approach to mitigating this problem is to increase the size of the cache. Increasing the size of the cache may improve performance, however, cache memory is expensive in comparison to the slower, lower level memory. It is therefore important to use cache memory space as efficiently as possible.
One way to improve the efficiency of a cache memory system and to decrease memory latency time is to attempt to anticipate processor requests and retrieve lines of data from the memory in advance. This technique is known as prefetching. Prefetching can be performed by noting dynamic properties of the reference data stream such as sequential and/or stride access. Alternatively, prefetching can be performed on the basis of stored information. This stored information might be related to patterns of access within or between pages, or to hints produced by the compiler and/or programmer.
In cache structures with prefetching, a common approach is to have a prefetch buffer which holds lines that have been prefetched. Having such a separate buffer avoids pollution of the cache proper due to mistaken prefetches. However, it is often difficult to coordinate the contents of such a prefetch buffer with logic that determines what to prefetch as a function of ongoing accesses, or stored information. In addition, searching a prefetch buffer may require multiple associative lookups for a single operation.